429C - Guess the Tree - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>

#define endl '\n'

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 30;
const int mod = 1e9 + 7;

int n;
int a[N], child[N];

void dfs(int u) {
    if (a[u] == 2) {
        cout << "NO" << endl;
        exit(0);
    }

    if (a[u] == 1 || u == 0) {
        cout << "YES" << endl;
        exit(0);
    }

    for (int i = n; i > u; i--) {
        if (child[i] + a[u] < a[i] && a[u] != a[i] - 1) {
            child[i] += a[u];
            dfs(u - 1);
            child[i] -= a[u];
        }
    }
}


void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    if (a[n] != n || n == 2) {
        cout << "NO" << endl;
        return;
    }

    dfs(n - 1);
    cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}